package Thethirdexperiment;

/**
 * Created by hasee on 2017/11/6.
 */
public class Searching
{
    //-----------------------------------------------------------------

    //  Searches the specified array of objects using a linear search

    //  algorithm. Returns null if the target is not found.

    //-----------------------------------------------------------------

    public static Comparable linearSearch (Comparable[] data,
                                           Comparable target)
    {
        Comparable result = null;
        int index = 0;

        while (result == null && index < data.length)
        {
            if (data[index].compareTo(target) == 0)
                result = data[index];
            index++;
        }

        return result;
    }

    //-----------------------------------------------------------------

    //  Searches the specified array of objects using a binary search

    //  algorithm. Returns null if the target is not found.

    //-----------------------------------------------------------------

    public static Comparable binarySearch (Comparable[] data,
                                           Comparable target)
    {
        Comparable result = null;
        int first = 0, last = data.length-1, mid;

        while (result == null && first <= last)
        {
            mid = (first + last) / 2;  // determine midpoint

            if (data[mid].compareTo(target) == 0)
                result = data[mid];
            else
            if (data[mid].compareTo(target) > 0)
                last = mid - 1;
            else
                first = mid + 1;
        }

        return result;
    }
    //顺序查找
    public static Comparable SequenceSearch(int a[], int value, int n)
    {
        int i;
        for(i=0; i<n; i++)
            if(a[i]==value)
                return i;
        return -1;
    }
    //二分查找（折半查找），版本1
    public static Comparable BinarySearch1(int a[], int value, int n)
    {
        int low, high, mid;
        low = 0;
        high = n-1;
        while(low<=high)
        {
            mid = (low+high)/2;
            if(a[mid]==value)
                return mid;
            if(a[mid]>value)
                high = mid-1;
            if(a[mid]<value)
                low = mid+1;
        }
        return -1;
    }
    //插值查找
    public static int InsertionSearch(int a[], int value, int low, int high)
    {
        int mid = low+(value-a[low])/(a[high]-a[low])*(high-low);
        if(a[mid]==value)
            return mid;
        if(a[mid]>value)
            mid =  InsertionSearch(a, value, low, mid-1);
        if(a[mid]<value)
            mid = InsertionSearch(a, value, mid+1, high);
        return mid;
    }


}
